package algorithms.betterqueue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @功能
 * @创建时间 2020/12/28
 */
public class IndexPQ {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(false, 0, nums);
        return ans;
    } public void dfs(boolean choosePre, int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        dfs(false, cur + 1, nums);
        if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
            return; }
        t.add(nums[cur]);
        dfs(true, cur + 1, nums);
        t.remove(t.size() - 1); }
    public  static void sort(Comparable[] a){
        int N = a.length;
        for(int k = N/2; k>=1; k--)
            sink(a,k,N);
        while (N>1){
            exch(a,1,N--);
            sink(a,1,N);
        }
    }
    private static void sink(Comparable[] a,int k,int N){
        while (2*k <=N){
            int j = 2*k;
            if(j < N&& less(a,j,j+1)) j++;
            if(!less(a,k,j)) break;
            exch( a,k,j);
            k=j;
        }
    }
    public  static boolean less(Comparable[]  a,int i,int j){
        return a[i].compareTo(a[j])<0;
    }
    public  static void exch(Comparable[]  a,int i,int j){
        Integer t= (Integer) a[i];
        a[i]=a[j];
        a[j]=t;
    }

}
